1. Field of the Invention
This invention generally relates to the methods and apparatus for determining the true minutia within a fingerprint for the purpose of the subsequent matching or comparing fingerprint minutia data sets, and more specifically relates to a minutia detector which determines a minutiae list from the association of a ridge skeletal image and a valley skeletal image and their independently determined minutiae.
2. Description of the Related Art
The appearance of fingerprints is well known. Closely spaced, generally parallel ridges of friction skin appear black on an inked fingerprint (or "print"). The ridges exhibit usually a generally circular flow around the center, or "core" of the print. Asai (U.S. Pat. No. 4,646,352, col.5, line 68) observes that, in general, one can tell where is the tip of the finger by looking at the ridge flow. People have a maximum ridge density of about 32 ridges/cm (Bunn, 4,641,350 column 4, line 44).
At specific points a ridge may terminate at a "ridge end" or may divide into two ridges at a "bifurcation". Other morphological events, such as "bridges", "islands" and "trifurcations" (McMahon, 4,208,651 col. 3, line 20; Riganati et al., 4,135,147 col. 4, line 67; Schiller, 4,752,966 col. 1, line 36), are known as well. These points are known as minutiae (singular, "minutia" ), and they number typically 50-200 on people's fingers (Riganati et al., 4,135,147 col. 5, line 36). Their disposition across the fingerprint, unique to the individual and to the finger, form a basis for using fingerprints to identify people.
In order to compare fingerprints, an automated system may implement typically, and very broadly speaking, processing in four steps on a digitized grey-level image of each given print. These are:
i) Preliminary Image Processing. This is a sequence of directional smoothing, filtration and contrast enhancement. Processing will include establishing a "direction map" of the apparent ridge flow. The direction map is an image whose values are circular, corresponding to traversing .pi. radians. Processing may include detection of areas which are blurred or unclear. The resultant grey-level image presumably has smaller local variations in image intensity and is clearer than the original.
ii) Binarization. Roughly, this turns all dark pixels black and all light pixels white. The process will usually take into account a direction map, similar to that used in Preliminary Image Processing, but applied now to the image input to this second step. The process may fit a directional filter matched to the average local ridge and valley structure. Ideally the resultant binary image will show thick, smooth black ridges.
iii) Skeletonization. The thick black ridges in the binary image are "thinned" down to one-pixel thickness. The result should be a skeletal image where long thin ridges are interrupted by locations which are obvious ridge ends or bifurcations.
iv) Minutia Identification. Given the skeletal image, all candidate ridge ends and bifurcations are identified. Repairs are made to the skeletal image where there are obvious problems with detail, and corresponding updates are performed on the corpus of candidate minutiae.
The last step, Minutia Identification, typically cannot resolve all problems with detail in the skeletal image. Hence, at the end of the processing outlined above, the resultant corpus of candidate minutiae usually contains "false" minutiae, ones that properly should not be used to match the print against others. These false minutiae are a serious problem for a fingerprint matcher that consumes minutiae, slowing down its processing while providing greater opportunity for false matching between prints. A matcher that depends on local relationships among minutiae has the further problem that these false minutiae will interrupt the true relationships. For instance, if the matcher needs the closest minutia to another, an interposed false minutia will mask the truly closest one.
Accordingly, it is an object of the present invention to reduce the number of these false minutiae.
False minutiae occur in areas of the skeletal image where the ridge morphology has been interpreted incorrectly. Many times a false "bridge" will connect two otherwise well behaved neighboring ridges. This failure derives often from a very dark local area of the acquired grey-level image, wherein the Binarizer does not interpose white valley pixels through the area. The Skeletonizer then, not having a continuous thin row of white pixels from which to start eroding the black, renders an interpretation of the local area as "H" instead of as "II".
Other failures, where the ridge structure has been thinned inappropriately, are often easy to see. In extremely untoward cases areas with poor morphology may look more like a "honeycomb" than like parallel ridges. Such problems can arise from several causes, including:
i) The direction maps of either Preliminary Image Processing or Binarization may fail to characterize properly the ridge flow, particularly in areas with high ridge curvature.
ii) Blur detection in Preliminary Image Processing may fail, leading to a failure properly to mask scarred or otherwise truly unclear areas of the print.
iii) The Binarizer may fail to characterize the local ridge and valley profile, especially when ridges are too thick near the crease of the first finger joint.
iv) Given the exigencies of connectivity of black areas in the binary image, some small local areas may reveal various anomalies in the Skeletonizer. These anomalies may tend to be subtle. Sometimes their interpretation of connectivity in places, while not wrong, may be unexpected.
Minutia Identification performs most of the requisite repairs. Each such repair involves a reduction in the number of apparent minutiae that reside on the skeletal image. Among such repairs are: repairing small breaks in ridges, eliminating small islands and ridge spurs, and eliminating small apparent "bubbles" in ridges. Many of these examples may derive from true conditions on the finger itself. Ridge spurs and other noted conditions are certainly known. Apparent bubbles often represent pores in the skin. But these true details cannot be distinguished easily from false details with similar skeletal morphology. In particular, apparent bubbles occur where the ridge thickness is much greater than average. Each such repair involves a reduction in the number of apparent minutiae that reside on the skeletal image.
Minutia Identification cannot resolve all problems with detail in the skeletal image. There is a limit to what can be done to repair a ridge skeleton without then beginning to destroy the structure about true minutiae. We would like another source of knowledge, in addition to the ridge skeleton itself. The natural dark-light symmetry of the fingerprint provides us additional information which can be used by the Minutia Detector.
For a normal, high-quality minutia to be derived from a clear ridge on the binary image, one would expect that the "inverse" part of the binary image about the ridge would be similarly clear. The white space interposed about the black ridges correspond to "valleys" between the ridges. A clear ridge end should be nestled in the "Y" of a "bifurcation" of the surrounding valley. Conversely, a clear ridge bifurcation should surround a valley "end". Hence, at least for minutiae limited to "endings" and "bifurcations", ridges and valleys "mirror" each other. Schiller (4,227,805 col. 1, line 10 and 4,752,966 col. 1, line 20) refers to minutiae of both ridges and valleys. Bowles et al. (4,525,859 col. 2, line 27) note that the terminations of valleys are ridge bifurcations. Also Davis (5,420,937) makes similar observations (see below).
It is in fact true, minutiae can be determined by either the processing of a ridge image or the processing of a valley image. It is also true that certain false minutiae can be detected using specific editing criteria embedded within either process. Either process used individually, however, retains a number of false minutiae which may be undesirable in a subsequent match process.
With the above background in mind, the inventors have recognized a need to provide a minutia detector that is more accurate in the elimination of false minutiae.